///**
// * Definition for singly-linked list.
// * public class ListNode {
// *     int val;
// *     ListNode next;
// *     ListNode() {}
// *     ListNode(int val) { this.val = val; }
// *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
// * }
// */
////重排链表
////做法就是把链表分成两半，然后再重合
//
//class Solution {
//    public void reorderList(ListNode head) {
//        if(head==null||head.next==null||head.next.next==null) return;
//        //快慢指针找到中间节点
//        ListNode fast=head;
//        ListNode slow=head;
//        while(fast!=null&&fast.next!=null){
//            fast=fast.next.next;
//            slow=slow.next;
//        }
//        //跳出循环之后，slow指的就是中间节点（双数为左的）
//        //中间节点之后的进行逆序
//        ListNode pre=null;
//        ListNode cur=slow.next;
//        ListNode next=cur.next;
//        slow.next=pre;//让前半条链尾节点指向空
//        while(cur!=null){
//            cur.next=pre;
//            pre=cur;
//            cur=next;
//            if(cur==null) break;
//            next=next.next;
//        }
//
//        //到这里之后，就被分成了两条链表
//        ListNode cur1=head;
//        ListNode cur2=pre;
//        ListNode newHead=new ListNode(0);
//        pre=newHead;
//        while(cur1!=null){
//            pre.next=cur1;
//            cur1=cur1.next;
//            pre=pre.next;
//
//
//            if(cur2!=null){
//                pre.next=cur2;
//                cur2=cur2.next;
//                pre=pre.next;
//            }
//        }
//    }
//}
